package com.gaogzhen.datastructure.linear.linkedList;

import java.util.LinkedList;

public class SingleCircularLinkedList<E> {
    transient Node<E> first;
    transient Node<E> last;
    transient int size;

    public SingleCircularLinkedList() {
    }

    public void add(E e) {
        if (size == 0)
            addFirst(e);
        else {
            Node<E> eNode = new Node<>(e, first);
            last.next = eNode;
            last = eNode;
            size++;
        }
    }

    private E unlink(Node<E> pre, Node<E> n) {
        if (size == 1)
            return unlinkLast();
        E item = n.item;
        if (n == first) {
            last.next = first.next;
            first.item = null;
            first.next = null;
            first = last.next;
        } else if (n == last) {
            pre.next = first;
            last.item = null;
            last.next = null;
            last = pre;
        } else {
            pre.next = n.next;
            n.item = null;
            n.next = null;
        }
        size--;
        return item;
    }

    private E unlinkLast() {
        E item = last.item;
        last.item = null;
        last.next = null;
        first = last = null;
        size = 0;
        return item;
    }

    public void addFirst(E e) {
        first = last = new Node<>(e, null);
        first.next = first;
        size = 1;
    }

    public int size() {
        return size;
    }
    private static class Node<E> {
        E item;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        SingleCircularLinkedList<Integer> circularLinkedList = new SingleCircularLinkedList<>();
        int num = 41, c = 3;
        for (int i = 1; i <= num; i++) {
            circularLinkedList.add(i);
        }
        Node<Integer> pre = circularLinkedList.last;
        Node<Integer> current = circularLinkedList.first;
        LinkedList<Integer> l = new LinkedList<>();
        int count = 0;
        while (circularLinkedList.size() > 1) {
            count++;
            if (count  == c) {
                l.add(circularLinkedList.unlink(pre, current));
                current = pre.next;
                count = 0;
            } else {
                pre = current;
                current = current.next;
            }
        }

        l.add(circularLinkedList.first.item);
        System.out.println(l);
    }
}
